home *** CD-ROM | disk | FTP | other *** search
/ World of Education / World of Education.iso / world_s / sp12src.zip / DICT.PAS < prev    next >
Pascal/Delphi Source File  |  1991-03-27  |  6KB  |  216 lines
  1. {$A+,B-,D-,E-,F+,G-,I+,L-,N-,O-,R-,S-,V+,X+}
  2. Unit Dict;
  3. Interface
  4. { DICT.PAS dictionary object and methods to create and use a superimposed
  5.   code dictionary.  Copyright Edwin T. Floyd, 1990, 1991. }
  6. Type
  7.   Dictionary = Object
  8.     DictArray : Pointer;  { Pointer to dictionary bit array }
  9.     DictCount : LongInt;  { Number of key entries in this dictionary }
  10.     DictSize : Word;      { Number of bytes in dictionary bit array }
  11.     DictBits : Byte;      { Number of bits per key entry }
  12.  
  13.     Constructor Init(MaxKeys : Word; BitsPerKey : Byte);
  14.     { Initialize dictionary, specify maximum keys and bits per key. }
  15.  
  16.     Constructor RestoreDictionary(FileName : String);
  17.     { Restore dictionary saved on disk by SaveDictionary }
  18.  
  19.     { Note: Use either Init or RestoreDictionary, not both. }
  20.  
  21.     Destructor Done;
  22.     { Release storage allocated to dictionary. }
  23.  
  24.     Function DictionarySize : Word;
  25.     { Returns number of bytes that will be written by SaveDictionary. }
  26.  
  27.     Procedure SaveDictionary(FileName : String);
  28.     { Save dictionary in a disk file. }
  29.  
  30.     Function InsertString(Var s : String) : Boolean;
  31.     { Insert string in dictionary; returns TRUE if string is already there. }
  32.  
  33.     Function StringInDictionary(Var s : String) : Boolean;
  34.     { Returns TRUE if string is in dictionary. }
  35.  
  36.     Function InsertBlock(Var Data; Len : Word) : Boolean;
  37.     { Insert block in dictionary; returns TRUE if block is already there. }
  38.  
  39.     Function BlockInDictionary(Var Data; Len : Word) : Boolean;
  40.     { Returns TRUE if block is in dictionary. }
  41.  
  42.     Function EstError : Real;
  43.     { Returns estimated probability of error. }
  44.  
  45.     Function ActError : Real;
  46.     { Returns actual probability of error (slow, counts bits). }
  47.  
  48.   End;
  49.  
  50. Function DictionaryBytes(MaxKeys : LongInt; BitsPerKey : Byte) : LongInt;
  51. { Returns the size in bytes of the optimal dictionary bit table for the
  52.   indicated key and bit-per-key counts. }
  53.  
  54. Implementation
  55.  
  56. Const
  57.   MagicNumber = $F501205E; { Used to validate dictionary save file }
  58.  
  59. Type
  60.   SaveFileHeader = Record
  61.   { Header for dictionary save file (all numbers are byte-reversed) }
  62.     Magic : LongInt;       { Magic number for validity test }
  63.     BitsCount : LongInt;   { Bits-per-key and entry count }
  64.     Size : Word;           { Size of dictionary bit map in bytes }
  65.   End;
  66.  
  67. Function CountBits(Var InBuf; InLen : Word) : LongInt;
  68. External; {FAR}
  69.  
  70. Function SetBloomFilter(Var InBuf; InLen : Word;
  71.   Var BitTable; BitTableLen, BitCount : Word) : Boolean;
  72. External; {FAR}
  73.  
  74. Function TestBloomFilter(Var InBuf; InLen : Word;
  75.   Var BitTable; BitTableLen, BitCount : Word) : Boolean;
  76. External; {FAR}
  77.  
  78. {$L BLOOM.OBJ }
  79.  
  80. Function LongSwap(n : LongInt) : LongInt;
  81. { Reverse bytes in a LongInt. }
  82. Inline(
  83.   $5A/                   {      pop    dx}
  84.   $58/                   {      pop    ax}
  85.   $86/$C4/               {      xchg   ah,al}
  86.   $86/$D6);              {      xchg   dh,dl}
  87.  
  88. Function DictionaryBytes(MaxKeys : LongInt; BitsPerKey : Byte) : LongInt;
  89. Begin
  90.   DictionaryBytes := Round(MaxKeys * BitsPerKey / (-Ln(0.5) * 8));
  91. End;
  92.  
  93. Constructor Dictionary.Init(MaxKeys : Word; BitsPerKey : Byte);
  94. Var
  95.   DictBytes : LongInt;
  96. Begin
  97.   DictBytes := DictionaryBytes(MaxKeys, BitsPerKey);
  98.   If DictBytes > $FFF0 Then Begin
  99.     WriteLn(DictBytes, ' bytes optimal for dictionary, but ', $FFF0,
  100.       ' is maximum size dictionary.  Using max size.');
  101.     DictBytes := $FFF0;
  102.   End Else If DictBytes > MaxAvail Then Begin
  103.     WriteLn(DictBytes, ' bytes optimal for dictionary, but only ', MaxAvail,
  104.       ' bytes are available.  Using ', MaxAvail);
  105.     DictBytes := MaxAvail;
  106.   End Else If DictBytes < 16 Then DictBytes := 16;
  107.   DictSize := DictBytes;
  108.   GetMem(DictArray, DictSize);
  109.   FillChar(DictArray^, DictSize, 0);
  110.   DictCount := 0;
  111.   DictBits := BitsPerKey;
  112. End;
  113.  
  114. Constructor Dictionary.RestoreDictionary(FileName : String);
  115. Var
  116.   Header : SaveFileHeader;
  117.   DictBytes : LongInt;
  118.   f : File;
  119.   OldMode : Byte;
  120. Begin
  121.   OldMode := FileMode;
  122.   FileMode := $40;
  123.   Assign(f, FileName);
  124.   Reset(f, 1);
  125.   BlockRead(f, Header, SizeOf(Header));
  126.   With Header Do Begin
  127.     Magic := LongSwap(Magic);
  128.     Size := Swap(Size);
  129.     DictBytes := FileSize(f) - SizeOf(Header);
  130.     If (Magic <> MagicNumber) Or (Size <> DictBytes) Or (Size < 16)
  131.     Or (Size > $FFF0) Then Begin
  132.       WriteLn('File ', FileName, ' is not a dictionary save file.');
  133.       Halt(1);
  134.     End;
  135.     DictSize := Size;
  136.     DictBits := BitsCount And $FF;
  137.     DictCount := LongSwap(BitsCount And $FFFFFF00);
  138.     GetMem(DictArray, DictSize);
  139.     BlockRead(f, DictArray^, DictSize);
  140.     Close(f);
  141.     FileMode := OldMode;
  142.   End;
  143. End;
  144.  
  145. Destructor Dictionary.Done;
  146. Begin
  147.   FreeMem(DictArray, DictSize);
  148.   DictArray := Nil;
  149.   DictSize := 0;
  150.   DictBits := 0;
  151.   DictCount := 0;
  152. End;
  153.  
  154. Function Dictionary.DictionarySize : Word;
  155. Begin
  156.   DictionarySize := DictSize + SizeOf(SaveFileHeader);
  157. End;
  158.  
  159. Function Dictionary.InsertString(Var s : String) : Boolean;
  160. Begin
  161.   InsertString := InsertBlock(s[1], Length(s));
  162. End;
  163.  
  164. Function Dictionary.StringInDictionary(Var s : String) : Boolean;
  165. Begin
  166.   StringInDictionary := BlockInDictionary(s[1], Length(s));
  167. End;
  168.  
  169. Function Dictionary.InsertBlock(Var Data; Len : Word) : Boolean;
  170. Begin
  171.   If SetBloomFilter(Data, Len, DictArray^, DictSize, DictBits)
  172.   Then InsertBlock := True Else Begin
  173.     Inc(DictCount);
  174.     InsertBlock := False;
  175.   End;
  176. End;
  177.  
  178. Function Dictionary.BlockInDictionary(Var Data; Len : Word) : Boolean;
  179. Begin
  180.   BlockInDictionary := TestBloomFilter(Data, Len, DictArray^, DictSize,
  181.     DictBits);
  182. End;
  183.  
  184. Procedure Dictionary.SaveDictionary(FileName : String);
  185. Var
  186.   Header : SaveFileHeader;
  187.   f : File;
  188. Begin
  189.   Assign(f, FileName);
  190.   ReWrite(f, 1);
  191.   With Header Do Begin
  192.     Magic := LongSwap(MagicNumber);
  193.     Size := Swap(DictSize);
  194.     BitsCount := LongSwap(DictCount) + DictBits;
  195.   End;
  196.   BlockWrite(f, Header, SizeOf(Header));
  197.   BlockWrite(f, DictArray^, DictSize);
  198.   Close(f);
  199. End;
  200.  
  201. Function Dictionary.EstError : Real;
  202. Begin
  203.   EstError := Exp(Ln(1.0-Exp(-(DictCount*DictBits)/(DictSize*8.0)))*DictBits);
  204. End;
  205.  
  206. Function Dictionary.ActError : Real;
  207. Var
  208.   AllBits, BitsOn : LongInt;
  209. Begin
  210.   AllBits := LongInt(DictSize) * 8;
  211.   BitsOn := CountBits(DictArray^, DictSize);
  212.   ActError := Exp(Ln(BitsOn / AllBits) * DictBits);
  213. End;
  214.  
  215. End.
  216.